Может быть, поставить подножку?

Верно: между пальцами; меж пальцами и меж пальцев.

И то и другое. Лапка - часть ноги насекомого.

http://commons.wikimedia.org/wiki/File:Insectanatomydiagram.svg?uselang=ru

Правильно: трется о ноги хозяина. И допустимо:  об ноги хозяина.

Предлог О с вин. падежом произносится без ударения (с переносом ударения – о бок). Употребляется (наряду с ОБ) перед формами, начинающимися согласными (в том числе "йот"), кроме форм местоименных слов всё, всю, все, всех, что (где выступает ОБО). Требует употребления форм местоименных слов с начальным Н (о него и об него).

Предлог ОБ с вин. падежом произносится без ударения (с переносом ударения – об пол, об руку, об стену). Употребляется перед формами, начинающимися гласными; наряду с О употребляется перед формами, начинающимися согласными (в том числе согласной "йот"), кроме форм местоименных слов всё, всю, все, всех, что (где выступает ОБО). Требует употребления форм местоименных слов с начальным Н (об него и о него).

Это сочетание не тавтологичное (тавтология – неоправданное соседство однокоренных слов, например: следует отметить следующие особенности), но плеонастичное (т. е. лексически избыточное), ведь ступня – это и есть нижняя часть ноги.